package com.lhcai.lc.category.prefixsum;

import java.util.HashSet;
import java.util.Set;

/**
 * 523. 连续的子数组和
 *
 * @author liuhuaicai
 * @since 2024-10-19 10:36
 */
public class Lc523 {
    public static void main(String[] args) {
        Lc523 lc523 = new Lc523();
        System.out.println(lc523.checkSubarraySum(new int[]{1, 0}, 2));
    }

    public boolean checkSubarraySum(int[] nums, int k) {
        int[] pre = new int[nums.length + 1];
        // 获取前缀和数组
        for (int i = 1; i <= nums.length; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= nums.length; i++) {
            set.add(pre[i - 2] % k);
            if (set.contains(pre[i] % k)) {
                return true;
            }
        }
        return false;
    }

    // 判断索引
//    public boolean checkSubarraySum(int[] nums, int k) {
//        if (nums.length < 2) {
//            return false;
//        }
//        Map<Integer, Integer> map = new HashMap<>();
//        map.put(0, -1);
//        int remainder = 0;
//        for (int i = 0; i < nums.length; i++) {
//            // 取余数
//            // 6 % 5 余 1，再加3，则 (1 + 3) % 5 等同于 (5 + 1 + 3) % 5
//            remainder = (remainder + nums[i]) % k;
//            if (map.containsKey(remainder)) {
//                if (i - map.get(remainder) >= 2) {
//                    return true;
//                }
//            } else {
//                map.put(remainder, i);
//            }
//        }
//        return false;
//    }

    // 暴力解法 超出时间限制
    // 94 / 101 个通过的测试用例

//    public boolean checkSubarraySum(int[] nums, int k) {
//        // 获取所有前缀和
//        int[] pre = new int[nums.length];
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//            pre[i] = sum;
//        }
//        // 先判断前缀和中是否存在
//        for (int i = 1; i < pre.length; i++) {
//            if (pre[i] % k == 0) {
//                return true;
//            }
//        }
//        // 则为求解，长度至少为2 的子串中，是否存在 K的倍数
//        for (int right = 2; right < pre.length; right++) {
//            for (int left = 0; left < right - 1; left++) {
//                int sub = pre[right] - pre[left];
//                if (sub % k == 0) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
}
